/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 */

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  coins.sort((a, b) => a - b);
  const dp = new Array(amount + 1).fill(-1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i += 1) {
    let min = Infinity;
    let coin = 0;
    let child = 0;
    for (let j = 0; j < coins.length; j += 1) {
      coin = coins[j];
      if (coin > i) {
        break;
      }
      child = dp[i - coin];
      if (child >= 0 && child < min) {
        min = child;
      }
    }
    if (min < Infinity) {
      dp[i] = min + 1;
    }
  }
  return dp[amount];
}

console.log(coinChange([1, 2, 5], 11) === 3);
console.log(coinChange([2], 3) === -1);
console.log(coinChange([1], 0) === 0);
console.log(coinChange([186, 419, 83, 408], 6249) === 20);
console.log(coinChange([227, 99, 328, 299, 42, 322], 9847) === 31);
console.log(coinChange([436, 83, 210, 75, 286], 3165) === 11);
